public class 接头密匙 {


    public static int MAXN = 500;
    // 每个数字使用 # 进行隔开, 负号也要算作一个字符, 所以 0 - 9 加上这两个字符需要有 12 条路径
    public static int[][] tree = new int[MAXN][12];// 0,1,2,3,4,5,6,7,8,9,-,#
    // 前缀树模板
    public static int[] pass = new int[MAXN];
    public static int[] end = new int[MAXN];
    public static int cnt;
    public int[] countConsistentKeys (int[][] b, int[][] a) {
        // 先将 a 加入前缀树中
        StringBuilder sb = new StringBuilder();
        for (int[] arr : a) {
            sb.setLength(0); // 将字符串设置为 0
            int n = arr.length; // 取一下当前数组长度
            for (int i = 0; i < n - 1; i++) { // 将两者之差全部都加入到 sb 中, 并用 # 隔开
                sb.append(arr[i + 1] - arr[i]);
                sb.append('#');
            }
            insert(sb.toString()); // 插入字符串
        }
        int[] ans = new int[b.length]; // 创建一个 ans 数组
        int x = 0; // ans 数组的指针
        for (int[] arr : b) {
            sb.setLength(0);
            int n = arr.length;
            for (int i = 0; i < n - 1; i++) {
                sb.append(arr[i + 1] - arr[i]);
                sb.append('#');
            }
            ans[x++] = preCount(sb.toString()); // 找到前缀字符串的值即可
        }
        return ans; // 返回一个 ans
    }






    public static void build () {
        cnt = 1;
    }

    public static void insert (String word) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < word.length(); i++) {
            int path = path(word.charAt(i));
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur]++;
    }

    public static void delete (String word) {
        if (count(word) > 0) {
            int cur = 1;
            for (int i = 0; i < word.length(); i++) {
                int path = path(word.charAt(i));
                if (--pass[tree[cur][path]] == 0) {
                    tree[cur][path] = 0;
                    return;
                }
                cur = tree[cur][path];
            }
            end[cur]--;
        }
    }

    private static int count(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = path(word.charAt(i));
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return end[cur];
    }

    private static int preCount(String pre) {
        int cur = 1;
        for (int i = 0; i < pre.length(); i++) {
            int path = path(pre.charAt(i));
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];
    }
    private static int path(char ch) {
        // 因为数字如果是200,301这种会乱掉, 引入 # 来进行结尾
        if (ch == '#') {
            return 11;
        } else if (ch == '-') {
            return 10;
        } else {
            return ch - '0';
        }
    }
}
